#include <string>
#include <stack>
using namespace std;

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        int len = s.length();
        for(int i = 0; i < len; i++) {
            if(stk.empty() == false) {
                switch (stk.top())
                {
                case '(': {
                    if(s[i] == ')') {
                        stk.pop();
                    } else {
                        stk.push(s[i]);
                    }
                    break;
                }
                case '{': {
                    if(s[i] == '}') {
                        stk.pop();
                    } else {
                        stk.push(s[i]);
                    }
                    break;
                }
                case '[': {
                    if(s[i] == ']') {
                        stk.pop();
                    } else {
                        stk.push(s[i]);
                    }
                    break;
                }
                }
            } else {
                stk.push(s[i]);
            }
        }
        return stk.empty();
    }
};